from collections import Counter
from typing import List



class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        n = len(power)
        power.sort()
        dp = power[:]
        def bisect(target):
            l = 0
            r = n - 1
            while l <= r:
                mid = (l + r) >> 1
                if power[mid] < target - 2:
                    l = mid + 1
                else:
                    r = mid - 1
            return l - 1
        max_val = [0] * n
        for i in range(n):
            if i and power[i] == power[i-1]:
                dp[i] = dp[i-1] + power[i]
            else:
                # 找小于 power[i] - 2 的最大
                idx = bisect(power[i])
                if idx >= 0:
                    dp[i] += max_val[idx]
            max_val[i] = max(max_val[i-1], dp[i])
        return max(dp)

if __name__ == '__main__':
    s = Solution()
    r = s.maximumTotalDamage([5,9,2,10,2,7,10,9,3,8])
    print(r)
